#include <iostream>
#include <stack>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> stack;
        TreeNode* node = root;
        int val = 0;
        int count = 0;
        while (node != nullptr) {
            if (node->left != nullptr) {
                stack.push(node);
                node = node->left;
            } else if (node->right != nullptr) {
                count++;
                if (count == k) {
                    return node->val;
                }
                node = node->right;
            } else {
                count++;
                if (count == k) {
                    return node->val;
                }
                while (stack.size() > 0) {
                    node = stack.top();
                    stack.pop();
                    count++;
                    if (count == k) {
                        return node->val;
                    }
                    if (node->right != nullptr) {
                        break;
                    }
                }
                node = node->right;
            }
        }
        return val;
    }
};

int main() {
    TreeNode t[2] = {TreeNode(2), TreeNode(1)};
    t[0].left = &t[1];
    Solution solution;
    int output = solution.kthSmallest(&t[0], 2);
    cout << output << endl;
}